#include <algorithm>
#include <cstdlib>  // Header file needed to use srand and rand
#include <iostream>
#include <unordered_set>
#include "dijkstra.h"

dijkstra::~dijkstra(){
    if(visited_){
        delete[] visited_;
        visited_ = nullptr;
    }
}

void  dijkstra::SetupTopology(Graph* graph){
    graph_ = graph;
    num_nodes_ = graph_->NodeSize();
    visited_ = new bool[num_nodes_];
    Q_tent = std::vector<std::priority_queue<Lable, std::vector<Lable>, cmp>>(num_nodes_);
    L_perm = std::vector<std::vector<Lable>>(num_nodes_);
}

std::vector<int> dijkstra::Intersection(std::vector<int> v1, std::vector<int> v2){
    std::unordered_set<int> result_set; // 用于存放结果
    std::unordered_set<int> nums_set(v1.begin(), v1.end());
        for (int num : v2) {
            // 发现v2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
    return std::vector<int>(result_set.begin(), result_set.end());
}

bool dijkstra::Judge(std::vector<int> v1,std::vector<int> v2){
    std::vector<int> result = Intersection(v1, v2); 
    //v1包含于v2返回true
    if(result.size()==v1.size()){
        return true;
    }else{
        return false;
    }
 }

 bool dijkstra::Lable_Judge(Lable& l1, Lable& l2){
    // 若l1优于l2，则返回true
    std::vector<int> CU1 = l1.CU;
    std::vector<int> CU2 = l2.CU;
    std::vector<int> result = Intersection(CU1, CU2); //求CU1和CU2的交集
    if(l1.weight<l2.weight && result.size()<=CU1.size()){
        return true;
    }else if (l1.weight<=l2.weight && result.size()<CU1.size())
    {
        return true;
    }else{
        return false;
    }
}

 void dijkstra::Relax_delay(Link* e, Lable l){
    int delay = e->delay;
    int delay_new = delay + l.weight;
    std::vector<int> CU_now = l.CU;
    std::vector<int> AU_now = e->A_units;
    int v_next = e->ter_id;
    //CU_new是AU_now和CU_now的交集
    std::vector<int> CU_new = Intersection(CU_now, AU_now);

    if(CU_new.empty()){
        return;
    }

    if(visited_[v_next-1]){
        return;
    }
    
    //std::cout<<v_next<<"\n";
    Lable l_new = {delay_new, e->link_id, e->link_state,CU_new};
    //在L_perm中删除掉次于l_new的标签
    for(auto iter=L_perm[v_next-1].begin();iter!=L_perm[v_next-1].end(); ){
    Lable temp = *iter;
     if( Lable_Judge(l_new, temp))
          iter = L_perm[v_next-1].erase(iter);
      else
            iter ++ ;    
    }
    //std::cout<<"L OK\n";
    //在Q_tent中删除掉次于l_new的标签
    std::vector<Lable> set_temp = {};
    for(int i=0; i<Q_tent[v_next-1].size();i++){
        if(!Q_tent[v_next-1].empty()){
            Lable temp = Q_tent[v_next-1].top();
            Q_tent[v_next-1].pop();
            if(Lable_Judge(l_new, temp)){
            }else{
                set_temp.emplace_back(temp);
            }
        }
    }
    for(int i = 0;i<set_temp.size();i++){
        Lable temp = set_temp[i];
        Q_tent[v_next-1].push(temp);
    }
    //std::cout<<"Q OK\n";
    Q_tent[v_next-1].push(l_new);
}

void dijkstra::Dijkstra_method(NodeId begin, NodeId end){
    for (int i = 0; i < num_nodes_; ++i) {
            visited_[i] = false;
        }    //初始化访问表
        Q_tent[begin-1].push(l_0);
        while(!Q_tent.empty()){ 
            Lable temp_l = {100, 0, 0, Omega};
            int mark = -1;
            for(int i = 0;i<num_nodes_;i++){
                if(!Q_tent[i].empty()){
                    if(temp_l.weight>Q_tent[i].top().weight){
                        temp_l = Q_tent[i].top();
                        mark = i; //记录temp_l对应的节点-1
                    }   
                }
            }
           
            NodeId temp_v =0;
            if(temp_l.Edge_id==0){
                temp_v = begin;
            }else{
                Link* temp_e = graph_->GetIdLinks(temp_l.Edge_id);
                //std::cout<<temp_l.Edge_id;
                temp_v = temp_e->ter_id;
            } 

             Q_tent[mark].pop(); //移出Q_tent
            L_perm[mark].emplace_back(temp_l); //加入L_perm
            visited_[mark] = true;

            //std::cout<<"Node__  "<<temp_v<<"\n";
            if(temp_v == end){
                break;
            }
            for(Link* edge_next: graph_->GetEgressLinks(temp_v)){
                Relax_delay(edge_next,temp_l);
            }
        }     
}

Path dijkstra::Trace_back(NodeId begin,NodeId end){
    Path result = Path();  //返回最终路线
    NodeId node_cur = end;
    Lable lable_cur = L_perm[node_cur-1][0];
    LinkId id_cur = lable_cur.Edge_id;
    int delay = lable_cur.weight;
    result.path_info.emplace_back(node_cur);
    result.delay = delay;
    while(node_cur!=begin){
        node_cur = graph_->GetIdLinks(id_cur)->source_id;
        result.path_info.emplace_back(node_cur);
        int temp_state = graph_->GetIdLinks(id_cur)->link_state;
        int temp_delay = graph_->GetIdLinks(id_cur)->delay;
        if(temp_state==2){
            delay -= 10;
        }else if(temp_state==1){
            delay -= 100;
        }
        delay -= temp_delay;  
        for(Lable l :L_perm[node_cur-1]){
            if(l.weight==delay){
                lable_cur = l;
            }
        }
        id_cur = lable_cur.Edge_id;  
    }
    return result;
}

Path dijkstra::FindPath(const Flow &flow){
    Path result = Path();
    NodeId begin = flow.from; //标记开始的节点
    NodeId end = flow.to;
    Dijkstra_method(begin, end);
    result = Trace_back(begin, end);
    return result;
    }
